\section{Algoritmo goloso constructivo}
\label{sec::greedy}

\subsection{Algoritmo y correctitud}

Como segundo m\'etodo de resoluci\'on del problema presentado, 
implementamos un algoritmo basado en una heur\'isitca golosa 
constructiva. La misma no siempre provee una soluci\'on exacta al
problema, pero nos permite implementar un algoritmo de tiempo 
polin\'omico en el tama\~no del grafo (dado por la cantidad de 
v\'ertices y aristas del mismo).

La heur\'istica puede resumirse de la siguiente manera:

\begin{quote}
	Empezamos con un conjunto $D$ vac\'io. Mientras $D$ no sea un 
	conjunto dominante, agregar un nodo $v$ con cantidad de vecinos
	(incluido si mismo, en este caso) sin dominar m\'axima.  
\end{quote}

Y la implementaci\'on no es mucho m\'as complicada, como se puede ver
detallada en el algoritmo de la figura~\ref{algo::greedy}.

\begin{algorithm}[H] 
	\caption{Pseudoc\'odigo para la heur\'istica golosa constructiva 
	utilizada en la resoluci\'on del problema de m\'inimo conjunto
	dominante. }
	\label{algo::greedy}
	\begin{algorithmic}
		\Function{goloso}{$G = (V,E), C \subseteq V$ componente}
			\State $D \gets \{ \}$
			\While{$D$ no domina $C$}
				\State $domina \gets 0, proximo$
				\ForAll{$v \in C \backslash D $}
					\State $N[v] \gets \{ v \} \bigcup \{ u | \text{$u$ no esta dominado. } \}$
					\If{$| N[v] | > domina$}
						\State $domina \gets | N[v] |$
						\State $proximo \gets v$ 
					\EndIf
				\EndFor
				\State $D \gets D \bigcup \{ proximo \}$
			\EndWhile
		\EndFunction
	\end{algorithmic}
\end{algorithm}

El algoritmo es polinomial (como veremos a continuaci\'on). Puesto que
el problema es NP-Completo, no suena probable que este algoritmo sea
\'optimo. De hecho, no lo es.

Tenemos el siguiente contraejemplo:

\begin{figure}[H]
	\caption{Contraejemplo a la optimalidad de la heur\'istica golosa constructiva}
	\label{fig::contragreedy}
	\centering
	\includegraphics[width=0.6\textwidth]{img/contragreedy.pdf}
\end{figure} 

En este caso, el algoritmo elige primero el nodo negro, y luego termina
eligiendo todos los nodos excepto los blancos. Suponiendo que el segundo
nivel tiene $k$ niveles, esto implica que el algoritmo goloso toma
$k+1+2k = 3k+1$. Sin embargo, se pueden elegir los nodos de color gris
claro y el nodo negro, con un total entonces de $2k+1$ nodos. Con lo 
cual utiliza $k$ nodos de m\'as en el conjunto dominante.

Si bien la proporci\'on en este caso es $\frac{3k+1}{2k+1} = 1 + \frac{k}{2k+1}$,
la cual esta acotada por 2, el error relativo de la heur\'istica golosa 
no esta acotado.  Puede demostrarse te\'oricamente que la estrategia considerada 
es una estrategia $O(\log n)$-aproximada.  Esta cota proviene de 
reducir la estrategia a una estrategia golosa muy conocida para el 
problema de m\'inimo conjunto dominante. M\'as detalles sobre esto puede
verse en ~\cite{greedyset}.

El algoritmo, como vemos, no es exacto y su error no esta acotado por 
una constante.

\subsection{Implementaci\'on en C++ y complejidad}

Para ver la complejidad, primero es necesario analizar la 
implementaci\'on en si.

Nuevamente, para el an\'alisis pr\'oximo supondremos $n$ la cantidad de
nodos del grafo y $m$ la cantidad de aristas.

La implementaci\'on efectiva del algoritmo en C++ consiste en el algoritmo
~\ref{algo::greedy} pero detallando las operaciones sobre conjuntos, de
manera de realizarlas lo m\'as eficientemente posible. 

Calculemos primero el costo computacional de la implementaci\'on 
realizada del ciclo interior del algoritmo.

Para recorrer todos los nodos no dominados, mantenemos un arreglo de 
enteros tal que la posici\'on \texttt{i} del arreglo nos dice si el nodo 
esta dominado o no. Mantenemos tambi\'en si
el nodo \texttt{i} esta o no en el conjunto dominante. Iterar sobre
todos los nodos de la componente conexa que no est\'an en el conjunto
dominante se realiza entonces en $O(n)$, porque en $O(1)$ podemos saber
si ese nodo o no esta ya en el conjunto dominante. Saber cuantos nodos
dominar\'ia si se lo agregara al conjunto dominante requiere recorrer
todos los vecinos del nodo que queremos agregar. Igual costo tiene, 
una vez elegido el nodo, actualizar todas las estructuras, porque esto 
involucra marcarlo como que est\'a en el conjunto dominante y marcar a 
sus vecinos como dominados.

Esta parte, puesto que consiste en iterar sobre todos los vecinos de
todos los nodos de la componente, tiene costo total $O(n+m)$ operaciones.

Posteriormente marcamos el nodo como dominante y agregamos sus vecinos.
Esto tiene costo $O(m)$ en peor caso, puesto que la cantidad de 
operaciones que realizamos esta acotada por la cantidad de vecinos del
nodo que agregamos, que en peor caso puede ser del \'orden de la 
cantidad de aristas del grafo.

Con esto tenemos en cuenta el costo del ciclo interno, en el que 
conseguimos el nodo para agregar al conjunto. Puesto que en toda
iteraci\'on agregamos al menos un nodo al conjunto dominante, y un 
conjunto dominante tiene menos de $n$ nodos, tenemos una cantidad total
de $O(n)$ iteraciones del ciclo principal. Por lo tanto el costo
computacional del ciclo principal del algoritmo goloso es $O(n(n+m)) =
O(n^2 + nm)$.

Finalmente, tenemos un costo adicional de $O(n)$ en reconstruir el
conjunto dominante utilizando para ello el arreglo que nos dice si un
nodo est\'a o no en el conjunto. Para esto necesitamos una nueva pasada
lineal, lo cual no modifica la complejidad total, que sigue siendo
$O(n^2+nm)$.
